package 剑指offer_leetcode;

/**
 * JZ79判断是不是平衡二叉树
 */
public class 剑指Offer55_II_平衡二叉树 {
    public boolean isBalanced(TreeNode root) {
        if(root==null)
            return true;
        int left = deep(root.left);
        int right = deep(root.right);
        if(Math.abs(left-right)>1)
            return false;
        return isBalanced(root.left) && isBalanced(root.right);
    }

    int deep(TreeNode root){
        if(root==null)
            return 0;

        return Math.max(deep(root.left),deep(root.right))+1;
    }

    //剪枝
    int deep2(TreeNode root){
        if(root==null)
            return 0;
        int left = deep(root.left);
        if(left==-1)
                return -1;
        int right = deep(root.right);
        if(right==-1)
                return -1;
        if(Math.abs(left-right)>1)
                return  -1;
        return Math.max(left,right)+1;
    }
    public boolean isBalanced2(TreeNode root) {
        if(root==null)
            return  true;
        if(deep(root)==-1)
            return false;
        return true;
    }

}
